/*
 * @Author: zxc
 * @Date: 2020-08-15 15:47:44
 * @LastEditTime: 2020-08-15 16:10:09
 * @LastEditors: zxc
 * @Description: 快速排序
 */
import { Compare, defaultCompare, swap } from "../utils";

export function fastSort(array, compareFn = defaultCompare) {
  return fast(array, 0, array.length - 1, compareFn);
}

function fast(array, left, right, compareFn) {
  let index;
  if (array.length > 1) {
    index = partition(array, left, right, compareFn);
    if (left < index - 1) {
      fast(array, left, index - 1, compareFn);
    }
    if (index < right) {
      fast(array, index, right, compareFn);
    }
  }
  return array;
}

function partition(array, left, right, compareFn) {
  const pivot = array[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;

  while (i <= j) {
    while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
      i++;
    }
    while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
      j--;
    }
    if (i <= j) {
      swap(array, i, j);
      i++;
      j--;
    }
  }
  return i;
}
